<!DOCTYPE html>
<html lang="en">
<head>
  <meta charset="UTF-8">
  <title>希尔排序</title>
</head>
<body>

</body>
</html>

<script>
  /*
  * 插入排序的改进版，克服了插入排序每次只能移动相邻位置的缺陷，希尔排序每次可以移动gap个位置  （不稳定）
  * */
  const arr = [ 22, 34, 3, 32, 82, 55, 89, 50, 37, 5, 64, 35, 9, 70 ]
  function sort (arr) {
    let len = arr.length
    let gap = Math.floor(len / 2)
    let q
    while (gap > 0) {
      for (let i = gap; i < len; i++) {
        q = i
        while (q >= gap && arr[q] < arr[q - gap]) {
          [ arr[q], arr[q - gap] ] = [ arr[q - gap], arr[q] ]
          // console.log('q:', q)
          // console.log('gap:', gap)
          q -= gap
        }
      }
      gap = Math.floor(gap / 2)
    }
    return arr
  }
  console.log('sotr:', sort(arr))
</script>